Many critically important and computationally demanding problems of interest to both government and industry require the solution of linear systems of equations whose coefficient matrix is both sparse and symmetric. There are available sophisticated numerical analysis techniques for enhancing the computational effectiveness of solution of such problems on single processor machines, but they fail to fully exploit the hidden parallelisms in such problems and in general have reached the limits of what can be accomplished in such an architecture.
Likewise there are available commercially a variety of powerful new multi-processor parallel-architecture computers, but there have been no general purpose tools for adapting an arbitrary problem to the full capabilities of such machines even in the ubiquitous case of basic linear algebra problems of the type described.
Thus, a need exists for a tool which can be used as a pre-processor in every kind of parallel-architecture computer and, without time-consuming individualized human preparation or interactive intervention, efficiently decompose any presented problem into an equivalent collection of smaller tasks which can be executed independently on different processors, thereby reducing both execution time and storage requirements.
Accordingly, it is an object of this invention to provide a method and apparatus for pre-processing the input data of any problem regarding solution of sparse symmetric linear systems of equations in such a manner as to decompose the problem into independently solvable smaller tasks which can be executed in parallel on the processors of an arbitrary parallel-architecture computer, and for allocation of these tasks to the different processors, and for operation of the processors in parallel during the execution of these tasks.
Another object of the present invention is to achieve such decomposition, allocation and operation in a manner which maximally exploits the sparsity structure (including the hidden parallelisms in such problems) to reduce storage requirements and execution time.